package Solutions

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
	_, _, b := dfs_45(root)
	return b
}

func dfs_45(root *TreeNode) (max int, min int, b bool) {
	if root == nil {
		return -(1<<31 - 1), 1<<31 - 1, true
	}

	min, max = (1<<31 - 1), -(1<<31 - 1)

	if root.Left != nil {
		maxL, minL, b := dfs_45(root.Left)
		if !b || root.Val <= maxL {
			return 0, 0, false
		}
		min = minL

	}
	if root.Right != nil {
		maxR, minR, b := dfs_45(root.Right)
		if !b || minR <= root.Val {
			return 0, 0, false
		}
		max = maxR
	}
	if root.Val > max {
		max = root.Val
	}
	if root.Val < min {
		min = root.Val
	}
	return max, min, true
}
